package niuke;

import java.util.ArrayList;
import java.util.List;

/**
 * @author lj
 * @Description: 二叉树的层次遍历-递归
 * @date 2020-10-27 15:03
 * @QQ 851477108
 */


public class erchashu1 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    //双层的levels用来存储节点
    List<List<Integer>> levels = new ArrayList<>();

    //传入辅助的level参数决定层次
    public void helper(TreeNode node,int level){
        //创建新一层
        if (levels.size() == level){
            levels.add(new ArrayList<>());
        }
        //节点加入对应层
        levels.get(level).add(node.val);
        //深度优先递归
        if (node.left != null){
            helper(node.left,level + 1);
        }
        if (node.right != null){
            helper(node.right,level + 1);
        }
    }

    public List<List<Integer>> levelOrder (TreeNode root) {
        // write code here
        if (root == null) return levels;
        helper(root,0);
        return levels;
    }
}
